发布于 

[学习笔记]树链剖分

[学习笔记]树链剖分

树链剖分。。。对这个名字还有点印象，记得好像是要分为轻链重链什么的，但是有没有写过已经完全忘记了。这次要进行一个树链剖分的专题。

介绍

树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。

原理及流程

原理

树链剖分有一个特点，它必须搭配其他数据结构如线段树、树状数组等来使用，而其本身并不是十分复杂。他其实一般只做了一件事--将一个无法使用线段树等数据结构解决的问题转化为可以使用这些数据结构的问题。

树链剖分，正如其名，是对树上的不同的链进行分离。其分离的主要依据轻链和重链。假设我们使用num[i]来存储以节点i为根节点的子树的节点数目，如果对于节点x,其子节点中num[]最大的便为节点x的重儿子，而连接他们的则为重边。其他儿子则为轻儿子，边为轻边。

当我们将一棵树中的所有边划分为重边和轻边时，我们会发现这棵树可以根据重边分为几个不同的链或点，相互连接的重边便为一条重链。而轻边的链则为轻链。

有了重链和轻链，这有什么用呢？树链剖分主要用来解决对两个点之间的最短路中的节点进行修改的问题。而树链剖分的思路便是通过重边和轻边重新生成一棵树，令每条重链中的所有元素在编号上连续。这样，当我们在更改最短路上的点时，我们便可以将其分为几条重链上的边，然后通过线段树来进行加速了。

步骤

实现树链剖分，我们一般需要两次dfs来建树，然后再用其他数据结构解决问题。当然，当数据规模较大时，我们一般会使用BFS来代替DFS，其原理都是相同的。

以下代码中用到的结构体如下:

1
2
3
4
5
6
7
struct Edge
{
trueint from,to;
trueint next;

trueEdge(int from=0,int to=0,int next=0):from(from),to(to),next(next)	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Node
{
trueint edge;

truevector<int> son;
trueint fa,top,num;
trueint id1,id2;
truebool flag;

trueNode(int id1):id1(id1)
true{
truetrueedge = 0;
truetruenum = 1;
truetrueflag = false;
true}
};

Node* f[MAXN];

第一次DFS

第一次DFS完成的是一些常规的操作:计算每个节点的深度、父节点、子节点和所有后代节点的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs1(Node* x)
{
trueint v = x->edge;

truewhile (v)
true{
truetrueNode *&t = e[v].to;
truetrueif (!f[t]->flag)
truetrue{
truetruetruef[t]->flag = true;
truetruetruef[t]->depth = f[x]->depth + 1;
truetruetruef[x]->son.push_back(t);
truetruetruef[t]->fa = x.id1;

truetruetruedfs1(f[t]);

truetruetruef[x]->num += f[t]->num;
truetrue}

truetruev = e[v].next;
true}
}

第二次DFS

此时需要算出重边和重儿子，然后在DFS时优先搜索重儿子，然后依序进行编号，这样的话可以令所有的重链中的节点编号连续。此外，我们需要记录每个点所在重链的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs2(Node* x,bool heavy)
{
truestatic cnt = 0;

trueif (heavy)
truetruex->top = x->fa->top;
truex->id2 = ++cnt;

trueint max = 0,maxi=0;
truefor (int i = 0; i<x->son.size(); i++)
truetrueif (x->son[i]->num > max)
truetrue{
truetruetruemax = x->son[i]->num;
truetruetruemaxi = i;
truetrue}

truedfs2(x->son[maxi],true);
truefor (int i = 0; i<x->son.size(); i++)
truetrueif (i!=maxi)
truetruetruedfs2(x->son[i],false);
}

使用

这里我们以对树中两点之间最短路上的点进行修改为例。假设我们想要修改x和y节点的最短路。那么我们进行以下几个操作:

  1. 使 fx = top[x], fy = top[y]。
  2. 比较fx与fy的深度，取深度较大的那个，假设为fx,然后对x到fx的范围进行更改。因为其编号连续，所以使用线段树更改速度较快。然后令x = fa[fx]。
  3. 重复1~2操作，直至fx == fy。
  4. 对x到y进行操作。

例题

题目来源: Luogu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <iostream>
#include <queue>

#define MAXN 100100

using namespace std;

int p;

/* 线段树部分 */

struct Segment
{
    int l, r;
    long long val, lazy;

    Segment *sonl, *sonr;

    Segment(int l, int r)
        :l(l), r(r), val(0), lazy(0), sonl(NULL), sonr(NULL)  {}
};

struct SegmentTree
{
    Segment *root;

    ~SegmentTree()
    {
        delete root;
    }

    void Update(Segment *segment)
    {
        segment->val = segment->sonl->val + segment->sonr->val;
truetruesegment->val %= p;
    }

    void PushDown(Segment *segment)
    {
        segment->sonl->lazy += segment->lazy;
        segment->sonl->val += segment->lazy * (segment->sonl->r - segment->sonl->l + 1);
truetruesegment->sonl->lazy %= p;
truetruesegment->sonl->lazy %= p;

        segment->sonr->lazy += segment->lazy;
        segment->sonr->val += segment->lazy * (segment->sonr->r - segment->sonr->l + 1);
truetruesegment->sonr->lazy %= p;
truetruesegment->sonr->lazy %= p;

        segment->lazy = 0;
    }

    void Build(Segment *segment, int a[])
    {
        if (root==NULL)
            root = segment;
        
        if (segment->l==segment->r)
        {
            segment->val = a[segment->l];
truetruetruesegment->val %= p;
        }else
        {
            int mid = (segment->l + segment->r)/2;
            segment->sonl = new Segment(segment->l, mid);
            segment->sonr = new Segment(mid+1, segment->r);

            Build(segment->sonl, a);
            Build(segment->sonr, a);

            Update(segment);
        }
    }

    void Add(Segment *segment, int l, int r, int val)
    {
        if (segment->l==l && segment->r==r)
        {
            segment->lazy += val;
            segment->val += val * (r - l + 1);
truetruetruesegment->lazy %= p;
truetruetruesegment->val %= p;

            return;
        }

        PushDown(segment);

        int mid = (segment->l + segment->r)/2;
        if (r<=mid)
            Add(segment->sonl, l, r, val);
        else if (l>mid)
            Add(segment->sonr, l, r, val);
        else{
            Add(segment->sonl, l, mid, val);
            Add(segment->sonr, mid+1, r, val);
        }
        Update(segment);
        return;
    }

    long long Query(Segment *segment, int l, int r)
    {
        if (segment->l==l && segment->r==r)
        {
            return segment->val;
        }

        PushDown(segment);
        int mid = (segment->l + segment->r)/2;
        if (r<=mid)
            return Query(segment->sonl, l, r);
        else if (l>mid)
            return Query(segment->sonr, l, r);
        else{
            long long ret = 0;
            ret += Query(segment->sonl, l, mid);
truetruetrueret %= p;
            ret += Query(segment->sonr, mid+1, r);
truetruetrueret %= p;

            return ret;
        }
    }
};

/* 树链剖分部分 */

struct Node
{
trueint val;
truestruct Edge *edge;
trueNode *fa;

trueint depth, size;
trueint id, endId;
trueNode *top;

trueNode()
true{
truetruedepth = 0;
truetruesize = 1;
truetrueedge = NULL;
truetruefa = NULL;
true}

}node[MAXN];

struct Edge
{
trueNode *from, *to;
trueEdge *next;

trueEdge(Node *from=NULL, Node *to=NULL)
truetrue:from(from), to(to), next(from->edge)	{}
};

queue<Node*> q;
void BuildTree(Node *x)
{
truefor (Edge *e = x->edge; e; e = e->next)
truetrueif (e && e->to->depth==0)
truetrue{
truetruetruee->to->fa = x;
truetruetruee->to->depth = x->depth + 1;

truetruetrueBuildTree(e->to);

truetruetruex->size += e->to->size;
truetrue}
truereturn;
}

int a[MAXN];
int num = 0;
void MakeId(Node *x)
{
truex->id = ++num;
truea[x->id] = x->val;

trueint maxn = 0;
trueNode *maxi = NULL;

truefor (Edge *e = x->edge; e; e = e->next)
truetrueif (e && e->to->fa==x && e->to->size > maxn)
truetrue{
truetruetruemaxn = e->to->size;
truetruetruemaxi = e->to;
truetrue}

trueif (maxi)
true{
truetruemaxi->top = x->top;
truetrueMakeId(maxi);
true}

truefor (Edge *e = x->edge; e; e = e->next)
truetrueif (e && e->to->fa==x && e->to !=maxi)
truetrue{
truetruetruee->to->top = e->to;
truetruetrueMakeId(e->to);
truetrue}
truex->endId = num;

truereturn;
}

inline void EdgeAdd(Node *x, Node *y, int z, SegmentTree *st)
{
truewhile (x->top != y->top)
true{
truetrueif (x->top->depth < y->top->depth)
truetruetrueswap(x, y);

truetruest->Add(st->root, x->top->id, x->id, z);

truetruex = x->top->fa;
true}
true
trueif (x->depth < y->depth)
truetrueswap(x, y);

truest->Add(st->root, y->id, x->id, z);

truereturn;
}

inline long long EdgeQuery(Node *x, Node *y, SegmentTree *st)
{
truelong long ret = 0;
truewhile (x->top != y->top)
true{
truetrueif (x->top->depth < y->top->depth)
truetruetrueswap(x, y);

truetrueret += st->Query(st->root, x->top->id, x->id);
truetrueret %= p;

truetruex = x->top->fa;
true}

trueif (x->depth < y->depth)
truetrueswap(x, y);

trueret += st->Query(st->root, y->id, x->id);
trueret %= p;

truereturn ret;
}

inline void SubtreeAdd(Node *x, int z, SegmentTree *st)
{
truest->Add(st->root, x->id, x->endId, z);
}

inline long long SubtreeQuery(Node *x, SegmentTree *st)
{
truereturn st->Query(st->root, x->id, x->endId) % p;
}

int main()
{	
trueint n, m, r;
truecin >> n >> m >> r >> p;

truefor (int i = 1; i<=n; i++)
true{
truetruenode[i].id = i;
truetruecin >> node[i].val;
true}

truefor (int i = 1; i<n; i++)
true{
truetrueint x, y;
truetruecin >> x >> y;

truetruenode[x].edge = new Edge(&node[x], &node[y]);
truetruenode[y].edge = new Edge(&node[y], &node[x]);
true}

truenum = 0;
truenode[r].depth = 1;
truenode[r].top = &node[r];
trueBuildTree(&node[r]);
trueMakeId(&node[r]);

trueSegmentTree *segmentTree = new SegmentTree();
truesegmentTree->Build(new Segment(1, n), a);

truefor (int i = 1; i<=m; i++)
true{
truetrueint opera;
truetruecin >> opera;

truetrueint x, y, z;
truetrueswitch(opera)
truetrue{
truetruetruecase 1: cin >> x >> y >> z;
truetruetruetruetrueEdgeAdd(&node[x], &node[y], z, segmentTree);
truetruetruetruebreak;

truetruetruecase 2: cin >> x >> y;
truetruetruetruetruecout << EdgeQuery(&node[x], &node[y], segmentTree) << endl;
truetruetruetruebreak;

truetruetruecase 3: cin>> x >> y;
truetruetruetruetrueSubtreeAdd(&node[x], y, segmentTree);
truetruetruetruebreak;

truetruetruecase 4: cin >> x;
truetruetruetruetruecout << SubtreeQuery(&node[x], segmentTree) << endl;
truetruetruetruebreak;
truetrue}
true}
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建，使用 Stellar 作为主题。